package com.链表;

import java.util.Stack;

/**
 * 给出一个以头节点 head 作为第一个节点的链表。链表中的节点分别编号为：node_1, node_2, node_3, ... 。
 *
 * 每个节点都可能有下一个更大值（next larger value）：对于 node_i，如果其 next_larger(node_i) 是 node_j.val，那么就有 j > i 且  node_j.val > node_i.val，而 j 是可能的选项中最小的那个。如果不存在这样的 j，那么下一个更大值为 0 。
 *
 * 返回整数答案数组 answer，其中 answer[i] = next_larger(node_{i+1}) 。
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/next-greater-node-in-linked-list
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class 链表中的下一个更大节点 {
        static class Solution {
            /**
             * 采用单调栈实现
             * @param head
             * @return
             */
        public int[] nextLargerNodes(ListNode head) {
            int[] arr = new int[10000];
            int[] dummy = new int[10000];
            Stack<Integer> stack = new Stack<>();
            int leng = 0 ;
            while (head != null){
                int value = head.val;
                dummy[leng] = value;
                while (!stack.empty() && value>dummy[stack.peek()]){
                    arr[stack.pop()] = value;
                }
                stack.add(leng);
                leng ++;
                head = head.next;
            }
            int[] cur = new int[leng];
            for(int i =  0;i<leng;i++){
                cur[i] = arr[i];
            }
            return cur;
        }

    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        ListNode head = new ListNode(new int[]{1, 1, 1, 1, 5});
        int[] i = solution.nextLargerNodes(head);

        for(int k:i){
            System.out.print(
                    k + " "
            );
        }
    }

}

